package algorithm.sort;
import java.util.Arrays;
  
public class NatureMergeSort {
  
    /** 
     * 自然合并算法 
     */  
    void MergeSort(int[] a, int n) {  
        int[] b = new int[n];  
        int s = 1;  
        while (s < n) {  
            MergePass(a, b, s, n);  
            s += s;  
            MergePass(b, a, s, n);  
            s += s;  
        }  
  
    }  
  
    void MergePass(int[] a, int[] b, int s, int n) {  
        int i = 0;  
        while (i <= n - 2 * s) {  
            Merge(a, b, i, i + s - 1, i + 2 * s - 1);  
            i = i + 2 * s;  
        }  
        if (i + s < n)  //小于等于？？？？？n   n-1的原因？？？？  
            Merge(a, b, i, i + s - 1, n-1 );  
        else  
            for (int j = i; j <= n - 1; j++)  
                b[j] = a[j];  
    }  
  
    void Merge(int[] a, int[] b, int left, int m, int right) {  
        int i = left;  
        int j = m + 1;  
        int k = left;  
  
        while (i <= m && right >= j) {  
            if (a[i] < a[j]) {  
                b[k++] = a[i++];  
  
            } else {  
                b[k++] = a[j++];  
  
            }  
        }  
  
        /* 
         * while (n <= i) { // 把左边数组剩余的数值放入数组b中 b[k++] = a[n++]; 
         *  
         * } while (m <= right) { // 把右边数组剩余的数值放入数组b中 b[k++] = a[m++]; 
         *  
         * } 
         */  
  
        if (i > m)  
            for (int q = j; q <= right; q++)  
                b[k++] = a[q];  
        else  
            for (int q = i; q <= m; q++)  
                b[k++] = a[q];  
  
    }  
  
    public static void main(String[] args) {  
        // TODO Auto-generated method stub
        // 程序也有点问题，如程序中的数组，最后一个1不会给出排序。
        int[] a = { 1, 10, 6, 9 ,1};
        NatureMergeSort ms = new NatureMergeSort();
        ms.MergeSort(a, a.length - 1);  
        System.out.println(Arrays.toString(a));  
  
    }  
  
}